<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2582：[Usaco2012Jan]Bovine Alliance</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2012Jan]Bovine Alliance</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2012Jan]Bovine Alliance</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2012Jan]Bovine Alliance                </h1>
                <p>时间限制：2s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div class="problem-text" align="left"><span style="font-size: medium"><span class="mono prewrap" id="probtext-text">&nbsp; Bessie and her bovine pals from nearby farms have finally decided that they are going to start connecting their farms together by trails in an effort to form an alliance against the farmers. The cows in each of the N (1 &lt;= N &lt;= 100,000) farms were initially instructed to build a trail to exactly one other farm, for a total of N trails. However months into the project only M (1 &lt;= M &lt; N) of these trails had actually been built. Arguments between the farms over which farms already built a trail now threaten to split apart the cow alliance. To ease tension, Bessie wishes to calculate how many ways the M trails that exist so far could have been built. For example, if there is a trail connecting farms 3 and 4, then one possibility is that farm 3 built the trail, and the other possibility is that farm 4 built the trail. Help Bessie by calculating the number of different assignments of trails to the farms that built them, modulo 1,000,000,007. Two assignments are considered different if there is at least one trail built by a different farm in each assignment. </span></span></div>
<div class="problem-text" align="left"></div>
<div class="problem-text" align="left"><span class="Apple-style-span" style="font-family: simsun; font-size: 14px; color: rgb(70, 70, 70); line-height: 21px; ">给出n个点m条边的图，现把点和边分组，每条边只能和相邻两点之一分在一组，点可以单独一组，问分组方案数。</span></div></p><hr/><h3>输入格式</h3><p><p><font size="4">* Line 1: Two space-separated integers N and M</font></p>
<p><font size="4">&nbsp;* Lines 2..1+M: Line i+1 describes the ith trail. Each line contains two space-separated integers u_i and v_i (1 &lt;= u_i, v_i &lt;= N, u_i != v_i) describing the pair of farms connected by the trail.&nbsp;&nbsp;Note that there can be two trails between the same pair of farms. </font></p></p><hr/><h3>输出格式</h3><p><p><font size="4">* Line 1: A single line containing the number of assignments of trails to farms, taken modulo 1,000,000,007. If no assignment satisfies the above conditions output 0.</font></p></p><hr/><h3>样例输入</h3><pre>5 4 
1 2
 3 2
 4 5
 4 5</pre><hr/><h3>样例输出</h3><pre> 6 </pre><hr/><h3>提示</h3><p><p><span style="font-size: medium">OUTPUT DETAILS: There are 6 possible assignments. Letting {a,b,c,d} mean that farm 1 builds trail a, farm 2 builds trail b, farm 3 builds trail c, and farm 4 builds trail d, the assignments are: {2, 3, 4, 5} {2, 3, 5, 4} {1, 3, 4, 5} {1, 3, 5, 4} {1, 2, 4, 5} {1, 2, 5, 4} </span></p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2582" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2582" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>